package backtracking;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class LeetCode22 {
    public static void main(String[] args) {
        LeetCode22 leetCode22 = new LeetCode22();
//        leetCode22.isValid("(())");
        leetCode22.generateParenthesis(3);
        leetCode22.result.stream().forEach(System.out::println);
    }
    List<String> result = new ArrayList<>();
    public List<String> generateParenthesis(int n) {
        StringBuilder stringBuilder = new StringBuilder(100);
        stringBuilder.append('(');
        backtrack(stringBuilder, n - 1, n);
        return result;
    }
    public void backtrack(StringBuilder s, int left, int right) {
        if(left == 0 && left == right && isValid(s.toString())){
            result.add(s.toString());
            s.deleteCharAt(s.length() - 1);
            return;
        }
        if(left > 0){
            backtrack(s.append('('), left - 1, right);
        }
        if(right > 0){
            backtrack(s.append(')'), left, right - 1);
        }
        s.deleteCharAt(s.length() - 1);
    }
    public boolean isValid(String s) {
        Stack<Character> left = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                left.push(s.charAt(i));
            } else if (s.charAt(i) == ')') {
                if(left.isEmpty()) return false;
                left.pop();
            }
        }
        return true;
    }
}
